package com.chapala.interviewquestions;

public class RemoveDuplicates {

	// No large addtional memory
	String removeDuplicateChars(String str) {

		char[] strChars = str.toCharArray();
		int length = str.length();
		int tail = length - 1;
		for (int i = 0; i < length; i++) {
			for (int j = i + 1; j <= tail; j++) {
				if (strChars[i] == strChars[j]) {
					System.out.println(strChars);
					System.out.println("Removing char at position" + j + ":" + strChars[j] + " whichmatches " + i + ":" + strChars[j]);
					for (int k = j; k < tail - 1; k++) {

						strChars[k] = strChars[k + 1];

					}
					j--;
					strChars[tail--] = 0;
					System.out.println(strChars);
				}
			}

		}
		return new String(strChars);

	}

	
	String removeDuplicateCharsV2(String str) {

		char[] strChars = str.toCharArray();
		int length = str.length();
		int tail = 1; // next unique char
		for (int i = 1; i < length; i++) {
			boolean uniqChar = true;
			System.out.println(str);;
			for (int j = 0; j < tail; j++) {
				if (strChars[i] == strChars[j]) {
					
					uniqChar = false;
					break;
				}
			}
			
		    if(uniqChar){
		    	strChars[tail] = strChars[i];
		    	tail++;
		    }

		}
		System.out.println(str);
		
			strChars[tail] = '\0';
		
		return new String(strChars);

	}
	
	
	public char[] removeDuplicates(String str1) {
		char[] str = str1.toCharArray();
		if (str == null) {
			return null;
		}
		int len = str.length;
		if (len < 2) {
			return str;
		}

		int tail = 1;

		for (int i = 1; i < len; ++i) {
			int j;
			for (j = 0; j < tail; ++j) {
				if (str[i] == str[j]) {
					break;
				}
			}

			if (j == tail) {
				System.out.println(str);
				System.out.println("Removing char at position " + i + ":" + str[i] + " whichmatches " + tail + ":" + str[tail]);
				str[tail] = str[i];
				++tail;
			}

		}
		for (; tail < len; tail++) {
			str[tail] = 0;
		}
		return str;

	}

	public static void main(String[] args) {
		//System.out.println(new RemoveDuplicates().removeDuplicates("aabbccddaabbccdd"));
		//System.out.println(new RemoveDuplicates().removeDuplicateChars("aaccbbddaabbccdd"));
		System.out.println(new RemoveDuplicates().removeDuplicateCharsV2("aaccbbddaabbccddefghijklmnopqrstuvwxyz"));
		

	}

}
